package com.leetcode;

import com.leetcode.common.TreeNode;

/**
 * 235. 二叉搜索树的最近公共祖先
 * 深度优先搜索, 递归写法
 * 判断的逻辑有些复杂
 *
 * @author fy
 * @date 2022/4/25 19:14
 */
public class Solution235 {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        // 如果p和q在root的两侧或者有一个节点和root重叠的话
        if ((root.val >= p.val && root.val <= q.val)
                || (root.val <= p.val && root.val >= q.val)) {
            return root;
        }
        // 如果都小于root的话, 那么两个节点在root左侧
        if (root.val > p.val && root.val > q.val) {
            return lowestCommonAncestor(root.left, p, q);
        }
        // 如果都大于root的话, 那么两个节点在root右侧
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        return null;
    }

}
